Embodiments of the present invention relate to content addressable memory (CAM) structures, and more particularly, to CAM structures that may be flexibly manipulated by a software program.
CAMs per se are well known. A CAM is a memory that can be accessed by its contents. The CAM typically includes various entries that store data. Each CAM entry includes value-matching logic that compares the data stored in the respective entry with an input value to determine if they are the same. When an input word is received, the input is compared bit-by-bit against each word stored in the CAM. Some CAMs require all bits of the input word to match all bits of one of the words stored in the CAM. Some require only predetermined bits to match. In any event, the comparisons performed by the various CAM entries are performed in parallel and provide very fast access to data.
Software programs, by contrast, identify operations to be performed by a microprocessor, digital controller, or the like (collectively, “processor”) in sequence. Typically, content searches in software require an iterative search throughout a number of data items until a value match is detected. Various algorithms have been proposed to reduce the number of iterations that are required to perform a search. A hash algorithm, for example, might use part of an input value as a direct index to a linked list of data. But, an iterative search through the linked list ultimately is required. Consider a system that lists customer records by telephone number. A hash table might use a portion of customer numbers (e.g., the last five digits) as an index to a hash table having 10,000 entries (10^n, where n is the number of digits by which the hash table is indexed). Each entry in the hash table would include a pointer to a linked list of entries. Each entry in the linked list would store the remainder of the number being searched, a pointer to a next item in the linked list if the entry is not a match, and a pointer to a data record associated with the customer if the entry is a match. Continuing with the foregoing example, a ten digit phone number might require linked lists of 10,000 entries each (10^l-n, where l is the total length of the search parameter and n is the length of the hash table index). To fully search for a phone number, an iterative review of the entire linked list might be required. A software program that performs a hash table lookup might be required to search and individually examine all 10,000 entries until it found a matching entry or until it concluded that there was no match at all. Of course, this iterative search can consume a great deal of time.
Accordingly, there is need in the art for a software controlled process that provides a parallel lookup of data.